package com.sakura.动态规划;

public class Code95_最长公共子序列 {


    // 暴力递归
    public int longestCommonSubsequence1(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        return f1(s1, s2, s1.length - 1, s2.length - 1);
    }

    private int f1(char[] s1, char[] s2, int p1, int p2) {
        if (p1 < 0 || p2 < 0) {
            return 0;
        }
        int ans1 = f1(s1, s2, p1 - 1, p2 - 1);
        int ans2 = f1(s1, s2, p1 - 1, p2);
        int ans3 = f1(s1, s2, p1, p2 - 1);
        int ans4 = s1[p1] == s2[p2] ? ans1 + 1 : 0;
        return Math.max(Math.max(ans1, ans2), Math.max(ans3, ans4));
    }

    // 递归优化版本
    public int longestCommonSubsequence2(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        return f1(s1, s2, s1.length, s2.length);
    }

    private int f2(char[] s1, char[] s2, int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f2(s1, s2, len1 - 1, len2 - 1) + 1;
        } else {
            ans = Math.max(f2(s1, s2, len1 - 1, len2), f2(s1, s2, len1, len2 - 1));
        }
        return ans;
    }


    // 记忆化搜索
    public int longestCommonSubsequence3(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[s1.length + 1][s2.length + 1];
        for (int i = 0; i < s1.length + 1; i++) {
            for (int j = 0; j < s2.length + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return f3(s1, s2, s1.length, s2.length, dp);
    }

    private int f3(char[] s1, char[] s2, int len1, int len2, int[][] dp) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        if (dp[len1][len2] != -1) {
            return dp[len1][len2];
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f3(s1, s2, len1 - 1, len2 - 1,dp ) + 1;
        } else {
            ans = Math.max(f3(s1, s2, len1 - 1, len2, dp), f3(s1, s2, len1, len2 - 1, dp));
        }
        dp[len1][len2] = ans;
        return ans;
    }


    // 动态规划
    public int longestCommonSubsequence4(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[s1.length + 1][s2.length + 1];
        // 如果len1 == 0， 那么必然没有共同子串，同理len2 == 0 也必然没有公共子串 所以 dp表中 i = 0 和 j 0 默认都是0
        for (int i = 1; i < s1.length + 1; i++) {
            for (int j = 1; j < s2.length + 1; j++) {
                // 递归怎么执行的 dp就怎么记录
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[s1.length][s2.length];
    }
}
